package algorithm;

/**
 * @author Panbo Guo
 * @date 2021/7/7
 */
public class T00035 {

    public static void main(String[] args) {
        int[] nums = {3,5,7,9,10};
        int target = 8;
        System.out.println(new Solution().searchInsert(nums, target));
    }

    static class Solution {
        public int searchInsert(int[] nums, int target) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            if (nums.length == 1) {
                int compare = Integer.compare(target, nums[0]);
                return compare == 0 ? 0 : compare < 0 ? 0 : 1;
            }
            int start = 0, end = nums.length - 1;
            while (start < end) {
                if (target < nums[start]) {
                    return start;
                }
                if (target > nums[end]) {
                    return end + 1;
                }
                if (target == nums[start]) {
                    return start;
                }
                if (target == nums[end]) {
                    return end;
                }
                int mid = (end + start) / 2;
                int compare = Integer.compare(target, nums[mid]);
                if (compare == 0) {
                    return mid;
                } else if (compare < 0) {
                    end = mid;
                } else {
                    start = mid + 1;
                }
            }
            return end;
        }
    }
}
